Giám mục Giáo phận Đà Nẵng Phanxicô Xaviê Nguyễn Quang Sách thỉnh nguyện Tòa Thánh cho một giám mục phó. Tuy vậy, thời gian kéo dài và giám mục Sách không được Tòa Thánh chấp thuận cho hồi hưu dù sức khỏe kém, và tuổi tác đã cao. Với sự giới thiệu của Thánh bộ Truyền giáo, Giáo hoàng đã chuẩn thuận bổ nhiệm ứng viên là linh mục Nguyễn Bình Tĩnh làm giám mục.[9] Ngày 10 tháng 5 năm 2000, Tòa Thánh công bố bổ nhiệm linh mục Phaolô Tịnh Nguyễn Bình Tĩnh, hiện là Giám đốc Đại Chủng viện Xuân Bích, Huế làm Giám mục Phó Giáo phận Đà Nẵng.[10][gc 1] Tân giám mục đã nhận nhiệm vụ giám mục ở tuổi "thất thập" với tâm trạng e ngại.[6][9]

Sáng sớm ngày 30 tháng 6 năm 2000, lễ tấn phong giám mục cho Giám mục Tân cử Nguyễn Bình Tĩnh được Giám mục Phanxicô Xaviê Nguyễn Quang Sách chủ sự, với phần nghi thức chính yếu do Giám mục Sách làm chủ phong với sự phụ phong của hai giám mục: Phaolô Bùi Văn Đọc (Giám mục chính tòa Giáo phận Mỹ Tho) và Giám mục Phêrô Trần Thanh Chung (Giám mục chính tòa Giáo phận Kon Tum). Lễ tấn phong diễn ra nhanh chóng do lo ngại về sức khỏe của Giám mục chính tòa Nguyễn Quang Sách đang chuyển biến xấu. Tham dự lễ tấn phong ngoài hai giám mục phụ phong, có 12 giám mục, 3 linh mục giám quản giáo phận. Số linh mục khoảng 240 vị. Khoảng 9.000 giáo dân có mặt từ lúc 3 giờ sáng để được sắp xếp tham dự buổi lễ. Lý do buổi lễ được tổ chức vào sáng sớm là do sức khỏe của Giám mục Nguyễn Quang Sách. Ngoài ra, các yếu tố khác như các nghi lễ được đơn giản hóa tối đa. Tông sắc chưa đến Việt Nam nhưng Giáo hoàng đặc cách cho tấn phong giám mục. Đáp từ trong buổi lễ, tân giám mục cho biết việc (bổ nhiệm) đến trong sự ngỡ ngạc của người trong cuộc. Ông tự nhận mình chỉ là một giám mục chuyển tiếp và bất đắc dĩ.[9]

Ngày 6 tháng 11 năm 2000, Giám mục Phanxicô Xaviê Nguyễn Quang Sách được chấp thuận đơn xin về hưu, với cương vị Giám mục phó, Giám mục Nguyễn Bình Tĩnh đương nhiên kế vị chức vụ Giám mục chính tòa Giáo phận Ðà Nẵng.[7] Năm 2001, Uỷ ban Linh mục, Tu sĩ và Chủng sinh trực thuộc Hội đồng Giám mục Việt Nam được phân tách thành hai ủy ban: Uỷ ban Giáo sĩ và Chủng sinh và Uỷ ban Tu sĩ. Giám mục Tĩnh được chọn làm Chủ tịch Tiên khởi của Uỷ ban Tu sĩ – Chủng sinh và giữ vai trò này trong một nhiệm kỳ, kéo dài đến năm 2004.[4][12] tháng 7 năm 2001, ông có dịp gặp với hồng y Phanxicô Xaviê Nguyễn Văn Thuận và cuộc gặp kéo dài vài giờ đồng hồ tại phòng riêng của hồng y Thuận.[13] Ông chính là người cho khởi công xây dựng công trình Tòa giám mục Đà Nẵng mới, trên phần đất chính ông xin từ chính quyền. Tuy vậy, công trình chưa kịp hoàn tất khi Giám mục Tĩnh hồi hưu.[14]

Năm 2002, Nguyễn Bình Tĩnh là giám mục duy nhất vắng mặt trong chuyến viếng thăm Ad Limina của Hội đồng Giám mục Việt Nam đến Rôma, dù không có giới hạn nào từ chính quyền Việt Nam.[15] Năm 2003, ông nhận định lạc quan về các quy định mới về kế hoạch hóa dân số, ví dụ như cấm sinh sản vô tính và mang thai hộ, do phù hợp với Giáo huấn Công giáo, tuy vậy cho phép các cặp vợ chồng hiếm muộn dùng các phương pháp kỹ thuật là không phù hợp với giáo huấn giáo hội.[16]

Ngày 13 tháng 5 năm 2006, Tòa Thánh công bố chấp nhận đơn xin về hưu của Giám mục Tĩnh, đồng thời bổ nhiệm linh mục Giuse Châu Ngọc Tri làm Giám mục chính tòa Giáo phận Đà Nẵng, kế vị Giám mục Tĩnh.[17] Lễ tấn phong cho Tân giám mục Giuse diễn ra ngay sau đó, vào ngày 4 tháng 8, do chính Giám mục Nguyễn Bình Tĩnh làm chủ phong,[14] giám mục phụ phong là các giám mục Stêphanô Nguyễn Như Thể – Tổng giám mục Tổng giáo phận Huế và Giám mục Antôn Vũ Huy Chương, giám mục chính tòa Giáo phận Hưng Hóa.[18] Giám mục Nguyễn Bình Tĩnh hưu dưỡng tại tu hội Xuân Bích tại Đà Nẵng.

Trong thời gian nghỉ hưu, Giám mục Nguyễn Bình Tĩnh vẫn thường tham gia các hoạt động mục vụ như cử hành lễ trao Bí tích Thêm Sức, thăm viếng các giáo dân, người nghèo và hỗ trợ những hoàn cảnh khó khăn. Năm 2010, Giáo phận Đà Nẵng tổ chức kỉ niệm 50 năm Linh mục, 10 năm Giám mục cho Giám mục Tĩnh, đánh dấu bằng lễ đồng tế có sự hiện diện của ba đời Giám mục chính tòa Giáo phận Đà Nẵng: Giám mục Phanxicô Xaviê Nguyễn Quang Sách, Giám mục Phaolô Tịnh Nguyễn Bình Tĩnh và Giám mục đương nhiệm Giuse Châu Ngọc Tri, ngoài ra cùng đồng tế còn có giám mục Giáo phận Phát Diệm Giuse Nguyễn Năng, quê hương Giám mục Tĩnh và đông đảo linh mục Giáo phận.[6] Ông hiện đã lẫn, không còn nhận ra người quen.[19]